package Tree;

public class 找树左下角的值 {
    private int maxDepth = -1;
    private int value = 0;

    public int findBottomLeftValue(TreeNode root) {
        // 迭代
        /*Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int result = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result = node.val;
            if(node.right != null) queue.offer(node.right);
            if(node.left != null) queue.offer(node.left);
        }
        return result;*/

        // 递归
        findLeftValue(root, 0);
        return value;
    }

    private void findLeftValue(TreeNode root, int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null && deep > maxDepth) {
            value = root.val;
            maxDepth = deep;
        }
        findLeftValue(root.left, deep + 1);
        findLeftValue(root.right, deep + 1);
    }
}
